RSA-KEM

RSA-KEM (RSA Key Encapsulation Method) — однопроходный (store-and-forward) механизм шифрования ключа для передачи в криптосистемах с открытым ключом. Сочетает в себе ложные перестановки RSA и KDF (Key Derivation Function). Обладает простотой и превосходными защитными свойствами, по сравнению с OAEP или OAEP+. Основной недостаток состоит в том, что шифротекст немного больше исходного текста.

Описание

Введение

RSA-KEM относится к классу криптографических методов инкапсуляции ключа, спроектированных для безопасной отправки симметричных ключей шифрования с использованием алгоритмов на открытых ключах. На практике, системы шифрования на основе открытых ключей неудобны для передачи длинных сообщений, вместо этого они используются для обмена симметричными ключами, которыми в итоге шифруется текст. Традиционным подходом к отправке симметричного ключа с помощью систем на открытых ключах является следующий алгоритм:

1. Генерация случайного числа.
2. Шифрование числа выбранным открытым ключом. Это зашифрованное сообщение отправляется получателю.
3. Получатель расшифровывает его закрытым ключом и восстанавливает симметричный ключ.

Представленный алгоритм имеет несколько недостатков. Во-первых, так как симметричный ключ мал, требуется его удлинение, а доказательство безопасности удлинения ключа не является строгим. Во-вторых, злоумышленник может отправить своё число, зашифрованное открытым ключом, и обмениваться сообщениями с получателем. В-третьих, не отслеживается целостность данных (обобщение второго пункта). Кроме того, шифры схожих сообщений могут быть похожими. Очевидно, что представленная схема недостаточно хороша и надёжна.

Метод инкапсуляции ключа демонстрирует иной, более продвинутый подход, решающий выявленные проблемы.

Процесс шифрования можно коротко представить следующим образом:

1. Генерируется случайное входное w.
2. Шифруется w с использованием RSA для передачи принимающему.
3. Генерируется материал ключа y = KDF(w) для использования в последующем шифровании.

Принимающий может восстановить w из принятого шифртекста и затем сгенерировать y, чтоб и отправитель и принимающий могли согласиться с одинаковым симметричным ключом.

Параметры

Механизм шифрования ключа имеет следующие системные параметры:

1. RSAKeyGen: алгоритм генерации ключа RSA.
2. KDF: A key derivation function.
3. KeyLen: положительное целое число.

Генерация ключа

Открытый ключ состоит из RSA коэффициента [math]\displaystyle{ n }[/math], который является произведением двух больших простых чисел и экспоненты [math]\displaystyle{ e }[/math], где [math]\displaystyle{ gcd(e, \phi(n)) = 1 }[/math] ([math]\displaystyle{ gcd }[/math] — наибольший общий делитель). Это так же выделяет key derivation function KDF. Пусть nLen обозначает длину n в байтах. Секретный ключ состоит из дешифровой экспоненты d, где [math]\displaystyle{ ed = 1 mod \phi(n) }[/math]. Алгоритм генерации ключа ничего не принимает на вход и выполняется следующим образом:

1. Вычисление (n, e, d) = RSAKeyGen().
2. Получение открытого ключа PK (public key).
3. Получение закрытого ключа pk (private key).

n, e, d — целые положительные числа.

Шифрование

Целью алгоритма шифрования является произвести псевдослучайный ключ K длины KeyLen и шифротекст [math]\displaystyle{ C_0 }[/math], который шифрует K. Алгоритм шифрования принимает следующее:

1. открытый ключ, состоящий из целого положительного n и e.
2. нет опций шифрования.

Выполняется следующим образом:

1) Генерируется случайное число [math]\displaystyle{ z \in [0 .. n) }[/math].

2) Шифруется [math]\displaystyle{ z }[/math] открытым ключом получателя [math]\displaystyle{ (n, e) }[/math]

[math]\displaystyle{ c = z^e mod n }[/math]

3) Число [math]\displaystyle{ c }[/math] преобразуется в шифрованную строку [math]\displaystyle{ C }[/math], а [math]\displaystyle{ z }[/math] в строчку [math]\displaystyle{ Z }[/math]

[math]\displaystyle{ C = intToStr(c, nLen), }[/math]

[math]\displaystyle{ Z = intToStr(z, nLen) }[/math]

4) Создаётся так называемый key-encrypting key(KEK), длиной [math]\displaystyle{ kekLen }[/math], с использованием Key Derivation Function(KDF):

[math]\displaystyle{ KEK = KDF(z, kekLen) }[/math]

5) Передаваемая информация оборачивается (в англ. литературе WRAP) ключом KEK, с использованием key-wrapping схемы. На выходе получим шифорованный текст [math]\displaystyle{ WK }[/math]

[math]\displaystyle{ WK = Wrap(KEK, K) }[/math]

6) Объединяем [math]\displaystyle{ C }[/math] и зашифрованный текст

[math]\displaystyle{ EK = C || WK }[/math]

[math]\displaystyle{ EK }[/math] является выходом алгоритма

Функция производства ключа (KDF)

KDF принимает на вход байтовую строчку и целое число [math]\displaystyle{ L \gt 0 }[/math]. Например, функция KDF1. Она параметризуется некоторой хеш функцией и определяется следующим образом: на вход идут аргументы [math]\displaystyle{ (Z, L) }[/math], на выходе получаем первые [math]\displaystyle{ L }[/math] байт выражения:

[math]\displaystyle{ Hash(Z }[/math] || [math]\displaystyle{ I2OSP(0, 4)) }[/math]|| ... || [math]\displaystyle{ Hash }[/math][math]\displaystyle{ (Z }[/math]||[math]\displaystyle{ I2OSP(k-1, }[/math] [math]\displaystyle{ 4)), }[/math]

где [math]\displaystyle{ k = L/Hash.outputLen. }[/math]

"Близнецом" функции KDF1 является KDF2. Она отличается от KDF1 лишь тем, что счётчик проходит от [math]\displaystyle{ 1 }[/math] до [math]\displaystyle{ k }[/math], а не от [math]\displaystyle{ 0 }[/math] до [math]\displaystyle{ k-1 }[/math]. Однако для этих функций трудно установить, насколько "хорошими" генераторами псевдослучайных чисел они являются. В связи с этой потенциальной уязвимостью желательно использовать функцию KDF3, например. Она принимает в качестве параметров Hash и [math]\displaystyle{ padding \geqslant 4. }[/math] На выход идут первые [math]\displaystyle{ L }[/math] байт выражения:

[math]\displaystyle{ Hash(I2OSP(0, padding) }[/math] || [math]\displaystyle{ Z) }[/math] || · · · || [math]\displaystyle{ Hash(I2OSP(k-1 }[/math], [math]\displaystyle{ padding) }[/math] || [math]\displaystyle{ Z), }[/math]

где [math]\displaystyle{ k = L/Hash.outputLen }[/math].

Рекомендуемые хеш-функции SHA1 и RIPMD-160. Рекомендуемый [math]\displaystyle{ padding = 4 }[/math]. О надёжности KDF3 уже можно судить достаточно уверенно. Функция [math]\displaystyle{ I2OSP }[/math] описанная в стандарте IEEE P1363, преобразует число в строку. Её работа основана на функции [math]\displaystyle{ OS2IP }[/math], которая наоборот, из строки получает число.

Схема обертки ключа (Key Wrapping Schema)

Спецификация RFC 5990 требует, чтобы в качестве схемы обертки использовалась одна из следующих:

1. AES Key Wrap
2. Triple-DES Key Wrap
3. Camillia Key Wrap

Наиболее распространена схема обертки AES. Она оперирует блоками по 64 бита и требует на вход сообщение длиной более одного такого блока. Если длина сообщения 64бита или меньше, постоянная определённая спецификацией и ключевая информация формируют единственный 128-битный блок, обертывание которого бессмысленно.

Дешифрование

Алгоритм дешифрования принимает на вход следующее:

1. закрытый ключ, состоящий из целого положительного n и d.
2. шифротекст [math]\displaystyle{ C_0 }[/math].

Выполняется следующим образом:

1. Разделение зашифрованной информации о ключе [math]\displaystyle{ EK }[/math] на шифротекст [math]\displaystyle{ C }[/math] длины [math]\displaystyle{ nLen }[/math] байт и обернутую информацию о ключе:
   
   [math]\displaystyle{ C || WK = EK }[/math]
   
   Если длина зашифрованной информации о ключе отличается от [math]\displaystyle{ nLen }[/math], то дешифрование прекращается с ошибкой.
2. Преобразование шифротекста [math]\displaystyle{ C }[/math] в целое число [math]\displaystyle{ c }[/math] и его расшифровка с использованием закрытого ключа принимающего:
   
   [math]\displaystyle{ c = StrToInt(C) }[/math]
   [math]\displaystyle{ z = c ^ d mod n }[/math]
   
   Если [math]\displaystyle{ c }[/math] не находится в пределах [math]\displaystyle{ 0 \leqslant c \leqslant n-1 }[/math], то дешифрование прекращается с ошибкой.
3. Преобразование целого [math]\displaystyle{ z }[/math] в байтовую строку [math]\displaystyle{ Z }[/math] длины [math]\displaystyle{ nLen. }[/math]
   
   [math]\displaystyle{ Z = IntToStr(z, nLen) }[/math]
   
   
4. Создание [math]\displaystyle{ KEK }[/math] длины [math]\displaystyle{ kekLen }[/math] байт из строки [math]\displaystyle{ Z }[/math] при помощи KDF:
   
   [math]\displaystyle{ KEK = KDF (Z, kekLen) }[/math]
   
   
5. Разворачивание информации о ключе [math]\displaystyle{ WK }[/math] при помощи [math]\displaystyle{ KEK }[/math]:
   
   [math]\displaystyle{ K = Unwrap (KEK, WK) }[/math]
   
   Если операция разворачивания прекращается с ошибкой, выполнение всего алгоритма прекращается с ошибкой.
6. Получение [math]\displaystyle{ K }[/math] на выходе алгоритма.

Оценка надёжности

Безопасность RSA-KEM может быть проанализирована в модели случайного оракула (Random Oracle Model, далее RO). Суть модели состоит в следующем. Предположим, что существует некая общедоступная функция обладающая такими свойствами:

1. На каждый новый аргумент функция отвечает новым значением и записывает пару (аргумент, значение) в таблицу.
2. Если аргумент уже встречался, то функция обратится к своей таблице и вернёт значение, соответствующее этому аргументу.

Доказательство основано на предположении, что KDF является случайным оракулом, и что решение обратной задачи RSA невозможно (проще говоря, RSA нельзя взломать). Для любого алгоритма генерации ключа для RSA (то есть алгоритма, возвращающего n, e и d), всегда выполнено n >= nBound (то есть nBound наименьшая допустимая граница для чисел n), и для каждого злоумышленника A справедливо:

[math]\displaystyle{ Advantage_{RSA-KEM}(A) \le Advantage_{RSA}(A') }[/math] + [math]\displaystyle{ qD/nBound (*), }[/math]

где [math]\displaystyle{ qD }[/math] — это максимальное число запросов к оракулу, которое может сделать злоумышленник для попытки разгадать шифр[math]\displaystyle{ A }[/math], AdvantageRSA-KEM(A) = |Pr[b*-b] - 1/2| — предсказательная способность А, AdvantageRSA(A') обозначает вероятность успешного решения инверсной задачи RSA. Нужно заметить, что приведённое выше неравенство не учитывает тот факт, что в реальности [math]\displaystyle{ RSA Key Gen }[/math] с ненулевой вероятностью возвращает «плохие» ключи. Чтобы учесть его, требуется лишь прибавить эту вероятность к правой части неравенства.

Приведём доказательство, рассматривая последовательность игр [math]\displaystyle{ G_{i} }[/math], и в каждой игре противник A проводит атаку. Каждая из этих игр проходит в одном вероятностном пространстве — меняются только правила того, как рассчитываются случайные величины. В каждой игре будет событие [math]\displaystyle{ S_{i} }[/math], связанное с событием [math]\displaystyle{ S_{0} }[/math]. Докажем, что разность [math]\displaystyle{ |Pr[S_{i}] - Pr[S_{i-1}]| }[/math] мала, и, более того, она будет свидетельствовать о том что в последней игре [math]\displaystyle{ Pr[S_{k}] = 1/2 }[/math]. Пусть [math]\displaystyle{ G0 }[/math] — первая игра, [math]\displaystyle{ S0 }[/math] — событие, обозначающее что [math]\displaystyle{ A }[/math] правильно угадывает бит [math]\displaystyle{ b }[/math] в игре [math]\displaystyle{ G0 }[/math]. Пусть [math]\displaystyle{ H }[/math] обозначает случайное предсказание оракула, размещающее элементы [math]\displaystyle{ Z_{n} }[/math] в битовые строчки длины [math]\displaystyle{ keyLen }[/math] в свою таблицу. Пусть [math]\displaystyle{ y^*\in Z_{n} }[/math] — атакуемый шифротекст, и [math]\displaystyle{ r^* = (y^*)^{1/e} \in Z_{n} }[/math]. Далее мы определим следующую игру [math]\displaystyle{ G1 }[/math], точно такую же как игру [math]\displaystyle{ G0 }[/math]. Если окажется так, что оракул был вызван для дешифрования с аргументом [math]\displaystyle{ y^* }[/math] раньше, и вызов был успешным, то игра останавливается. Пусть [math]\displaystyle{ S1 }[/math] — событие в игре [math]\displaystyle{ G1 }[/math], соответствующее событию [math]\displaystyle{ S0 }[/math]. Пусть [math]\displaystyle{ F1 }[/math] — событие, сигнализирующее о том, что игра [math]\displaystyle{ G1 }[/math] была остановлена. Понятно, что

[math]\displaystyle{ Pr[F1] \le qD/nBound, }[/math]

и в промежуток времени, когда игры [math]\displaystyle{ G0 }[/math] и [math]\displaystyle{ G1 }[/math] проходят одинаково, а именно, до того момента как случается [math]\displaystyle{ F1 }[/math], выполняется следующая лемма:

Пусть [math]\displaystyle{ E, E' }[/math] и [math]\displaystyle{ F }[/math] — события, определённые на пространстве случайных событий таким образом, что

[math]\displaystyle{ Pr[E }[/math] [math]\displaystyle{ \land }[/math] [math]\displaystyle{ \neg }[/math] [math]\displaystyle{ F] = Pr[E' }[/math] [math]\displaystyle{ \land }[/math] [math]\displaystyle{ \neg }[/math][math]\displaystyle{ F] }[/math]

Тогда выполняется:

[math]\displaystyle{ |Pr[E] }[/math][math]\displaystyle{ -Pr[ }[/math][math]\displaystyle{ E']| }[/math] [math]\displaystyle{ \le Pr[F]. }[/math]

В нашем случае [math]\displaystyle{ |Pr[S0] }[/math][math]\displaystyle{ -Pr[S1]| }[/math] [math]\displaystyle{ \le }[/math] [math]\displaystyle{ qD/nBound. }[/math] Далее определим игру [math]\displaystyle{ G2 }[/math], такую же как [math]\displaystyle{ G1 }[/math], за исключением того, что атакуемый шифротекст генерируется в начале игры, и если противник запрашивает [math]\displaystyle{ H }[/math] для [math]\displaystyle{ r^* }[/math], игра останавливается. Пусть [math]\displaystyle{ S2 }[/math] &mdash событие в [math]\displaystyle{ G2 }[/math], соответствующее событию [math]\displaystyle{ S0 }[/math]. Очевидно, что

[math]\displaystyle{ Pr[S2] = 1/2 }[/math]

в силу того, что ключ [math]\displaystyle{ H(r^*) }[/math] независим от чего-либо, доступного противнику в игре [math]\displaystyle{ G2 }[/math]. В этой игре [math]\displaystyle{ H }[/math] в [math]\displaystyle{ r^* }[/math] вызывается только с целью шифрования.

Пусть [math]\displaystyle{ F2 }[/math] — событие, сигнализирующее о том, что предыдущая игра прервалась. Понятно, что игры [math]\displaystyle{ G1 }[/math] и [math]\displaystyle{ G2 }[/math] протекают одинаково до тех пор, пока не случится [math]\displaystyle{ F2 }[/math], и, следовательно, по лемме мы получим:

[math]\displaystyle{ |Pr[S1]-Pr[S2]| }[/math][math]\displaystyle{ \le Pr[F2] }[/math]

Потребуем, чтобы [math]\displaystyle{ Pr[F2] \le Advantage_{RSA}(A') }[/math] для алгоритма A', время работы которого ограничено временем, описанным выше. Тогда неравенство (*) будет выполнено. Алгоритм А' запускается следующим образом. Он получает на вход случайный RSA модуль [math]\displaystyle{ n }[/math], RSA экспоненту [math]\displaystyle{ e }[/math] и случайный элемент [math]\displaystyle{ y* \le Zn }[/math]. A' создаёт открытый ключ, используя [math]\displaystyle{ n }[/math] и [math]\displaystyle{ e }[/math], а затем разрешает противнику A начать игру. Когда А вызывает оракул для шифрования, А' отвечает А парой [math]\displaystyle{ (K^*, y^*) }[/math], где [math]\displaystyle{ K^* }[/math] — случайный бит строки длиной [math]\displaystyle{ keyLen }[/math], а [math]\displaystyle{ y^* }[/math] подаётся на вход A. Алгоритм A' симулирует случайное предсказание [math]\displaystyle{ H }[/math], как и дешифрующее RO, следующим образом. Для каждого входного [math]\displaystyle{ r \le Z_{n} }[/math] для случайного предсказания A' вычисляет [math]\displaystyle{ y = r^e \in Z_{n} }[/math], и размещает [math]\displaystyle{ r }[/math], [math]\displaystyle{ y }[/math] и случайное значение [math]\displaystyle{ K = H(r) }[/math] в таблицу. Однако, если [math]\displaystyle{ y = y^* }[/math] А' вместо того выводит [math]\displaystyle{ r }[/math] и завершается. Когда противник A предоставляет шифротекст [math]\displaystyle{ y \in Z_{n} }[/math] дешифрующему предсказанию, А' ищет значение [math]\displaystyle{ y }[/math] в описанной таблице, чтобы определить было ли вычислено значение случайного предсказания при [math]\displaystyle{ r = y^{(1/e)} \in Z_{n} }[/math]. Если да, то А' отвечает дешифрующему предсказанию значением [math]\displaystyle{ K = H(r) }[/math], хранящемся в таблице. Иначе, алгоритм создаёт новый случайный ключ [math]\displaystyle{ K }[/math], и размещает пару [math]\displaystyle{ (y, K) }[/math] во второй таблице. Более того, если в будущем противник А должен будет вычислить случайное предсказание при [math]\displaystyle{ r \le Z_{n} }[/math] таком что [math]\displaystyle{ r^e = y }[/math], то ключ [math]\displaystyle{ K }[/math], сгенерированный выше, будет использован как значение [math]\displaystyle{ H(r) }[/math]. Понятно, что A' отлично симулирует А, и даёт на выходе решение для данного случая RSA с вероятностью [math]\displaystyle{ Pr[F2] }[/math]. Это и доказывает безопасность алгоритма. Количественно можно проверить, что RSA-KEM обеспечивает лучшую защиту по сравнению с RSA-OAEP+ и RSA-OAEP. Это преимущество выражается тем более, чем больше число сообщений, зашифрованных одним открытым ключом (замоделировано в BBM00). Это можно показать воспользовавшись тем, что решение инверсионной задачи RSA является очень трудозатратным. Таким образом безопасность RSA-KEM совсем не уменьшается с возрастанием числа зашифрованных текстов. Нужно заметить, что это утверждение справедливо только если число r в алгоритме шифрования для Simple RSA выбрано равномерно по модулю n, либо, как минимум, его распределение должно быть неотличимо от равномерного с точки зрения вычислений. Кроме прочего, RSA-KEM, в отличие от RSA-OAEP or RSA-OAEP+, нельзя назвать «хрупким» алгоритмом, то есть не найдены возможности для атак на его реализации.

Ссылки

• V. Shoup. A Proposal for an ISO Standard for Public Key Encryption. Preprint, December 2001. Архивная копия от 5 июля 2008 на Wayback Machine
• FCD 18033-2 Encryption algorithms — Part 2: Asymmetric ciphers. Архивная копия от 24 декабря 2010 на Wayback Machine
• Securing RSA-KEM via the AES (недоступная ссылка)
• RSA Algorithm Архивная копия от 22 ноября 2010 на Wayback Machine
• The Random Oracle Methodology Архивная копия от 3 марта 2016 на Wayback Machine
• Use of the RSA-KEM Key Transport Algorithm Архивная копия от 26 октября 2014 на Wayback Machine
• AES Key Wrap Specification Архивная копия от 17 сентября 2008 на Wayback Machine